/** CLASS MINIMAX TREE */
//package team2;

import java.util.Vector;

import javax.swing.tree.DefaultTreeModel;

//import team2.project2_AI.Player;

/*
 * Class Minimax Tree
 * 
 * Minimax Tree creates and stores the decision tree for making valid moves.
 */

/**
 *
 * @author Jill Greczek, Julio Montero, Brandon Jarratt
 */
public class MinimaxTree extends DefaultTreeModel
{

	private static final long serialVersionUID = 1L;
	private int depth;
	private Player playerColor;

	/** The root of the tree. */
    public MinimaxNode minimaxRoot;

    /** The state of the board. */
    public Player[][] boardState;
    
    /** Vector of flipped pieces. */
    Vector<Object> flippedPieces = new Vector<Object>();

    /** Creates an empty MinimaxTree. */
    public MinimaxTree(MinimaxNode minimaxRoot)
    {
    	super(minimaxRoot);
    }

    /** Copies the boardState for modification. */
    public Player[][] copy(Player[][] boardState){
    	
    	Player[][] boardcopy = new Player[8][8];
    	
    	for(int i = 0; i<boardState.length; i++){
    		for(int j = 0; j<boardState[i].length; j++){
    			boardcopy[i][j] = boardState[i][j];
    		}
    	}
    	return boardcopy;
    }
    
    /** Creates a MinimaxTree given a board state and depth. */
    public MinimaxTree(Player[][] bState, int d, MinimaxNode mRoot, Player color)
    {
    	super(mRoot);
    	minimaxRoot = mRoot;
    	boardState = bState;
    	depth = d;
    	playerColor = color;
    	/** For every potential move, compute the goodness function for that potential state. */
    	//!!! depth must be an even number
    	makeTree(copy(boardState), 1, minimaxRoot);
    }
    
    /** Creates the MinimaxTree using recursion. */
    public void makeTree(Player[][] bState, int d, MinimaxNode froot){
    	//if depth is reached, stop extending the tree
    	if(d != depth){
    		
    		Player turnColor;
    		
    		if(d % 2 != 0){
    			turnColor = playerColor;
    		}
    		else{
    			turnColor = opposite(playerColor);
    		}
    		Vector<int[]> moves = validMoves(bState, turnColor);
    		//for each move, create a child node
    		for(int i = 0; i<moves.size(); i++){
    			MinimaxNode temp = new MinimaxNode(moves.elementAt(i), goodnessFunction(bState, moves.elementAt(i)));
    			froot.add(temp);
    		}
    		//call makeTree on the child nodes until 'depth'
    		for(int i = 0; i<froot.getChildCount(); i++){
    			MinimaxNode child = (MinimaxNode)froot.getChildAt(i);
    			makeTree(getModifiedState(bState, turnColor, child.getMove()), d+1, child);
    		}
    	}
    }
    
    /** Checks if a potential move is valid, and updates the board if it is. */
    public boolean isValidMove(Player[][] bState, Player color, int[] move)
    {
    	int row = move[0];
    	int col = move[1];
    	Boolean legalMove = false;
        int r = 0; 
        int c = 0;
        
        boolean occupied = false;
		boolean blankspace = false;
        
        Player opponent = opposite(color);
    	
    	/** A piece must be captured - there must be a piece of your color after the piece of your opponent's color. */
    	
    	/* Check first to see if the space selected by the move is inside the board edges, and if the space is empty. */
    	if (col < 0 || col >= 8 || row < 0 || row >= 8)
		{
			return false;
		}
		if (bState[row][col] != Player.EMPTY)
		{
		    return false;
		}
		
		/* One of the surrounding pieces must be of the opposite color. Check up, down, left, right, up-right, up-left,
		 * down-right, down-left. */
		
		//Up
		// If the piece above yours is ON THE BOARD and the opponent's color
		if (row - 1 >= 0 && bState[row - 1][col] == opponent){
			
			occupied = false;
			blankspace = false;
			
			// For each piece above the opponent piece that is also the opponent color (not blank)
			for (r = row - 2; r >= 0 && !occupied && !blankspace; --r){
				//If a piece of your color is there, it's occupied
				if (bState[r][col] == color){
					occupied = true;
					break;
				}
				//If a blank space is there, it's empty
				else if (bState[r][col] == Player.EMPTY){
					blankspace = true;
					break;
				}
			}	
			//If your piece is above the opponent's piece
			if (occupied){
				//Flip all pieces between the placed piece and the other piece of your color
				return true;
			}
		}
		
		//Down
		//If the piece below yours is on the board and the opponent's color
		if (row + 1 < 8 && bState[row + 1][col] == opponent){
			
			occupied = false;
			blankspace = false;
			
			//For each piece below your piece, check for a sequence of opponent colors
			for (r = row + 2; r < 8 && !occupied && !blankspace; ++r){
				//If we find a piece of your color, capture
				if (bState[r][col] == color){
					occupied = true;
				}
				//if we find a blank space, you did it wrong
				else if (bState[r][col] == Player.EMPTY){
					blankspace = true;
				}
			}	
			//If we find a piece of your color, you did good
			if (occupied){
				return true;
			}
		}
		
		//Left
		if (col - 1 >= 0 && bState[row][col - 1] == opponent){
			
			occupied = false;
			blankspace = false;
			
			for (c = col - 2; c >= 0 && !occupied && !blankspace; --c){
				if (bState[row][c] == color){
					occupied = true;
				}
				else if (bState[row][c] == Player.EMPTY){
					blankspace = true;
				}
			}	
			if (occupied){
				return true;
			}
		}
		
		//Right
		if (col + 1 < 8 && bState[row][col + 1] == opponent){
			
			occupied = false;
			blankspace = false;
			
			for (c = col + 2; c < 8 && !occupied && !blankspace; ++c){
				if (bState[row][c] == color){
					occupied = true;
				}
				else if (bState[row][c] == Player.EMPTY){
					blankspace = true;
				}
			}
			if (occupied){
				return true;
			}
		}
		
		//Up-left
		if (col - 1 >= 0 && row - 1 >= 0 && bState[row - 1][col - 1] == opponent){
			
			occupied = false;
			blankspace = false;

			for (c = col - 2, r = row - 2; c >= 0 && r >= 0 && !occupied && !blankspace; --c, --r){
				if (bState[r][c] == color){
					occupied = true;
				}
				else if (bState[r][c] == Player.EMPTY){
					blankspace = true;
				}
			}
			if (occupied){
				return true;
			}
		}
		
		//Up-right
		if (col + 1 < 8 && row - 1 >= 0 && bState[row - 1][col + 1] == opponent){
			
			occupied = false;
			blankspace = false;

			for (c = col + 2, r = row - 2; c < 8 && r >= 0 && !occupied && !blankspace; ++c, --r){
				if (bState[r][c] == color){
					occupied = true;
				}
				else if (bState[r][c] == Player.EMPTY){
					blankspace = true;
				}
			}
			if (occupied){
				return true;
			}
		}
		
		//Down-left
		if (col - 1 >= 0 && row + 1 < 8 && bState[row + 1][col - 1] == opponent){
			
			occupied = false;
			blankspace = false;

			for (c = col - 2, r = row + 2; c >= 0 && r < 8 && !occupied && !blankspace; --c, ++r){
				if (bState[r][c] == color){
					occupied = true;
				}
				else if (bState[r][c] == Player.EMPTY){
					blankspace = true;
				}
			}
			if (occupied){
				return true;
			}
		}
		
		//Down-right
		if (col + 1 < 8 && row + 1 < 8 && bState[row + 1][col + 1] == opponent){
			
			occupied = false;
			blankspace = false;

			for (c = col + 2, r = row + 2; c < 8 && r < 8 && !occupied && !blankspace; ++c, ++r){
				if (bState[r][c] == color){
					occupied = true;
				}
				else if (bState[r][c] == Player.EMPTY){
					blankspace = true;
				}
			}
			if (occupied){
				return true;
			}
		}
    	return false;
		
    }
    
    /** Flips pieces assuming the move is valid */
    public Player[][] flipPieces(Player[][] bState, Player color, int[] move){
    	int row = move[0];
    	int col = move[1];
        int r, c;      
        Player opponent = opposite(color);
    	
    	//Up
		// If the piece above yours is ON THE BOARD and the opponent's color
		if (row - 1 >= 0 && bState[row - 1][col] == opponent){
			
			boolean occupied = false;
			boolean blankspace = false;
			
			// For each piece above the opponent piece
			for (r = row - 2; r >= 0 && !occupied && !blankspace; --r){
				//If a piece of your color is there, it's occupied
				if (bState[r][col] == color){
					occupied = true;
				}
				//If a blank space is there, it's empty
				else if (bState[r][col] == Player.EMPTY){
					blankspace = true;
				}
			}	
			//If your piece is above the opponent's piece
			if (occupied){
				//Flip all pieces between the placed piece and the other piece of your color
				for (r = row - 1; bState[r][col] == opponent; --r)
				{
					bState[r][col] = color;
					flippedPieces.addElement(bState[r][col]);
				}
			}
		}
		
		//Down
		//If the piece below yours is on the board and the opponent's color
		if (row + 1 < 8 && bState[row + 1][col] == opponent){
			
			boolean occupied = false;
			boolean blankspace = false;
			
			//For each piece below your piece, check for a sequence of opponent colors
			for (r = row + 2; r < 8 && !occupied && !blankspace; ++r){
				//If we find a piece of your color, capture
				if (bState[r][col] == color){
					occupied = true;
				}
				//if we find a blank space, you did it wrong
				else if (bState[r][col] == Player.EMPTY){
					blankspace = true;
				}
			}	
			//If we find a piece of your color, you did good
			if (occupied){
				//Flip all pieces between the placed piece and the other piece of your color
				for (r = row + 1; bState[r][col] == opponent; ++r)
				{
					bState[r][col] = color;
					flippedPieces.addElement(bState[r][col]);
				}
			}
		}
		
		//Left
		//For each piece to the left of your piece that is of the opponent's color
		if (col - 1 >= 0 && bState[row][col - 1] == opponent){
			
			boolean occupied = false;
			boolean blankspace = false;
			
			//For every opponent color piece in sequence to the left of your piece
			for (c = col - 2; c >= 0 && !occupied && !blankspace; --c){
				//If we find one of your color, we can capture
				if (bState[row][c] == color){
					occupied = true;
				}
				//If we find a blank space, the move is invalid
				else if (bState[row][c] == Player.EMPTY){
					blankspace = true;
				}
			}
			if (occupied){
				//If we find one of your color, capture the pieces
				for (c = col - 1; bState[row][c] == opponent; --c)
				{
					bState[row][c] = color;
					flippedPieces.addElement(bState[row][c]);
				}
			}
		}
		
		//Right
		//For each piece to the right of your piece that is your opponent's color
		if (col + 1 < 8 && bState[row][col + 1] == opponent){
			
			boolean occupied = false;
			boolean blankspace = false;
			
			for (c = col + 2; c < 8 && !occupied && !blankspace; ++c){
				if (bState[row][c] == color){
					occupied = true;
				}
				else if (bState[row][c] == Player.EMPTY){
					blankspace = true;
				}
			}
			if (occupied){
				//If we find a piece of your color, capture pieces
				for (c = col + 1; bState[row][c] == opponent; ++c)
				{
					bState[row][c] = color;
					flippedPieces.addElement(bState[row][c]);
				}
			}
		}
		
		//Up-left
		//For each piece to the 'up-left' of your piece that is your opponent's color
		if (col - 1 >= 0 && row - 1 >= 0 && bState[row - 1][col - 1] == opponent){
			
			boolean occupied = false;
			boolean blankspace = false;

			for (c = col - 2, r = row - 2; c >= 0 && r >= 0 && !occupied && !blankspace; --c, --r){
				if (bState[r][c] == color){
					occupied = true;
				}
				else if (bState[r][c] == Player.EMPTY){
					blankspace = true;
				}
			}
			if (occupied){
				//Capture pieces
				for (c = col - 1, r = row - 1; bState[r][c] == opponent; --c, --r)
				{
					bState[r][c] = color;
					flippedPieces.addElement(bState[r][c]);
				}
			}
		}
		
		//Up-right
		if (col + 1 < 8 && row - 1 >= 0 && bState[row - 1][col + 1] == opponent){
			
			boolean occupied = false;
			boolean blankspace = false;

			for (c = col + 2, r = row - 2; c < 8 && r >= 0 && !occupied && !blankspace; ++c, --r){
				if (bState[r][c] == color){
					occupied = true;
				}
				else if (bState[r][c] == Player.EMPTY){
					blankspace = true;
				}
			}
			if (occupied){
				//Capture pieces
				for (c = col + 1, r = row - 1; bState[r][c] == opponent; ++c, --r)
				{
					bState[r][c] = color;
					flippedPieces.addElement(bState[r][c]);
				}
			}
		}
		
		//Down-left
		if (col - 1 >= 0 && row + 1 < 8 && bState[row + 1][col - 1] == opponent){
			
			boolean occupied = false;
			boolean blankspace = false;

			for (c = col - 2, r = row + 2; c >= 0 && r < 8 && !occupied && !blankspace; --c, ++r){
				if (bState[r][c] == color){
					occupied = true;
				}
				else if (bState[r][c] == Player.EMPTY){
					blankspace = true;
				}
			}
			if (occupied){
				//Capture pieces
				for (c = col - 1, r = row + 1; bState[r][c] == opponent; --c, ++r)
				{
					bState[r][c] = color;
					flippedPieces.addElement(bState[r][c]);
				}
			}
		}
		
		//Down-right
		if (col + 1 < 8 && row + 1 < 8 && bState[row + 1][col + 1] == opponent){
			
			boolean occupied = false;
			boolean blankspace = false;

			for (c = col + 2, r = row + 2; c < 8 && r < 8 && !occupied && !blankspace; ++c, ++r){
				if (bState[r][c] == color){
					occupied = true;
				}
				else if (bState[r][c] == Player.EMPTY){
					blankspace = true;
				}
			}
			if (occupied){
				//Capture pieces
				for (c = col + 1, r = row + 1; bState[r][c] == opponent; ++c, ++r)
				{
					bState[r][c] = color;
					flippedPieces.addElement(bState[r][c]);
				}
			}
		}
		
		/* Finally, set the actual move space to the player's color. */
		bState[row][col] = color;
		flippedPieces.addElement(bState[row][col]);
		
		return bState;
    }
    
    /** Returns all valid moves (a Vector of arrays of ints) that a Player can make this turn. */
    public Vector<int[]> validMoves(Player[][] bState, Player color)
    {
    	Vector<int[]> vMoves = new Vector<int[]>();
    	/** Iterate through each space on the board and check its validity. If it is a valid move, add it to the vector.*/
    	
    	for(int i = 0; i<boardState.length; i++){
    		for(int j = 0; j<boardState[i].length; j++){
    			int[] move = new int[2];
    			move[0] = i;
    			move[1] = j;
    			if(bState[i][j] == Player.EMPTY)
    			{
	    			if(isValidMove(bState, color, move)){
	    				vMoves.add(move);
	    				
	    			}
    			}
    		}
    	}
    	return vMoves;
    }
    
    /** Computes the total number of pieces lost for all options given a root node, used for determining avg */
    /** There is a better way to implement this, with pointers, maybe, but Java is not C++ */
    public int sum = 0;
    public int count = 0; //counts number of leaf nodes
    public void piecesLost(MinimaxNode current){
    	if(isLeaf(current))
    	{
    		count++;
    		sum+=current.getGoodnessValue();
    	}
    	else
    	{
    		for(int chindex = 0; chindex < getChildCount(current); chindex++)
    		{
    			piecesLost((MinimaxNode) getChild(current,chindex));
    		}
    	}
    }

    /** pruning - move in the direction of the minimum (average) pieces lost */
    public MinimaxNode prune() {
    	//depth is determined in the constructor of MinimaxTree by the difficulty level, so the leaf nodes
    	//  are the min values we want to average
    	if(minimaxRoot.getChildCount() == 0)
    	{
    		//there is no move to make
    		int[] bad = new int[2];
    		bad[0] = -1;
    		bad[1] = -1;
    		return new MinimaxNode(bad, -999);
    	}
    	else
    	{
    		MinimaxNode best = (MinimaxNode) getChild(minimaxRoot,0);
    		int lost = 9999;
    		//for each child (potential move) of the root node (our turn), find and compare the average min values
	    	for(int chindex = 0; chindex < getChildCount(minimaxRoot); chindex++)
	    	{
	    		MinimaxNode current = (MinimaxNode) getChild(minimaxRoot,chindex);
	    		int currentLost = 0;
	    		
	    		//compute average pieces lost
	    		piecesLost(current);
	    		currentLost = -sum/count;
	    		
	    		if(currentLost < lost){
	    			best = current;
	    		}
	    	}
	    	return best;
    	}
    }

    /** Returns the modified state given a potential move. (Implements effects of the move) */
    public Player[][] getModifiedState(Player[][] currentState, Player color, int[] potentialMove){
    	
    	Player[][] modifiedState = currentState;
    	if(isValidMove(modifiedState, color, potentialMove)){
    		modifiedState = flipPieces(modifiedState, color, potentialMove);
    	}

    	return modifiedState;
    }

    /** Returns the number of pieces the player would have if they made that move. */
    public int getNumPieces(Player[][] currentState, Player color, int[] potentialMove){
    	
    	int initialPieces = 2;
    	int numPieces = 0;
    	
        if(isValidMove(currentState, color, potentialMove)){
        	numPieces = initialPieces + flippedPieces.size();
        	initialPieces = numPieces;
            flippedPieces.clear();
        }

        return numPieces;
    }

    /** Returns the number of edge pieces the player would have if they made that move. */
    public int getNumEdgePieces(Player[][] currentState, Player color, int[] potentialMove) {
    
        Vector<Object> edgePieces = new Vector<Object>();
        
        if(isValidMove(currentState, color, potentialMove)){
        	/* Check the top edge. */
        	for(int i = 0; i < 7; i++){
        		if(flippedPieces.contains(currentState[0][i])){
        			edgePieces.add(currentState[0][i]);
        			}
        	}
        	
        	/* Check the left edge. */
        	for(int i = 0; i < 7; i++){
        		if(flippedPieces.contains(currentState[i][0])){
        			edgePieces.add(currentState[i][0]);
        			}
        	}
        	
        	/* Check the bottom edge. */
        	for(int i = 0; i < 7; i++){
        		if(flippedPieces.contains(currentState[7][i])){
        			edgePieces.add(currentState[7][i]);
        			}
        	}
        	
        	/* Check the right edge. */
        	for(int i = 0; i < 7; i++){
        		if(flippedPieces.contains(currentState[i][7])){
        			edgePieces.add(currentState[i][7]);
        			}
        	}
        	flippedPieces.clear();
        }
        
        return edgePieces.size();
    }

    /** Returns the number of corner pieces the player would have if they made that move. */
    public int getNumCornerPieces(Player[][] currentState, Player color, int[] potentialMove) {

        Vector<Object> cornerPieces = new Vector<Object>();

        if(isValidMove(currentState, color, potentialMove)){
        	if(flippedPieces.contains(currentState[0][0])){
        		cornerPieces.add(currentState[0][0]);
        	}
        	if(flippedPieces.contains(currentState[0][7])){
        		cornerPieces.add(currentState[0][7]);
        	}
        	if(flippedPieces.contains(currentState[7][0])){
        		cornerPieces.add(currentState[7][0]);
        	}
        	if(flippedPieces.contains(currentState[7][7])){
        		cornerPieces.add(currentState[7][7]);
        	}
        }
        return cornerPieces.size();
    }

    /** Calculate the next move. */
    public int[] getNextMove() 
    {
    	return prune().getMove();
    }

    /** The goodness function for this action. */
    public int goodnessFunction(Player[][] bState, int[] potentialMove) 
    {
    	return getNumPieces(bState, playerColor, potentialMove) + 
    		3*getNumEdgePieces(bState, playerColor, potentialMove) + 
    		2*getNumCornerPieces(bState, playerColor, potentialMove);
    }
    
    /** Returns the opposite of the color (opponent's color) */
    public Player opposite(Player player){
        
    	Player opponent = Player.EMPTY;
    	/* Set opponent color. */
        if (player == Player.BLACK){
        	opponent = Player.WHITE;
        }
        else if (player == Player.WHITE){
        	opponent = Player.BLACK;
        }
        else {System.err.println("The player must have a color!");}
        
        return opponent;
    }

}

    
